⟸ pàgina anterior ⟸

Exercici 3 (Tasca 2).

(regular languages, concatenation, minimization of DFAs)

La concatenació de llenguatges regulars és regular

1. Construeix el DFA mínim per al llenguatge L_1\cdot L_2, on

   1. L_1=\{xaya\mid x,y\in\{a,b\}^*\} i L_2=\{bxby\mid x,y\in\{a,b\}^*\}.
   2. L_1=\{xaay\mid x,y\in\{a,b\}^*\} i L_2=\{bxb\mid x\in\{a,b\}^*\}.
   3. L_1=\{xaya\mid x,y\in\{a,b\}^*\} i L_2=\{bxb\mid x\in\{a,b\}^*\}.

   Trobeu els DFAs mínims que reconeixen L_1 i L_2. A partir d’ells, construïu un \lambda-NFA A que reconegui el llenguatge. Finalment, fent servir la construció de subconjunts, feu A determinista i minimitzeu el DFA obtingut.

2. Donats dos DFAs A i B com a entrada, quin és el cost de construir un DFA per a L(A) \cdot L(B)?